//+------------------------------------------------------------------+
//|                                                    Introsort.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+

//+------------------------------------------------------------------+
//| Introsort<TKey, TItem> 结构体：内省排序（混合排序算法）实现          |
//| 核心定位：融合三种排序算法的优势，解决单一排序算法的性能缺陷，实现“平均高效+最坏最优”的排序效果 |
//| 算法融合逻辑（优先级从高到低）：                                  |
//|  1. 小数据量（≤16个元素）：使用**插入排序**（简单高效，常数时间开销低）； |
//|  2. 中等数据量+递归深度未超限：使用**快速排序**（平均时间复杂度 O(n log n)，缓存友好）； |
//|  3. 递归深度超限（避免快速排序最坏情况 O(n²)）：切换为**堆排序**（最坏时间复杂度 O(n log n)，稳定性高）； |
//| 核心特性：                                                      |
//|  1. 双数组支持：同时处理“键数组（TKey）”和“值数组（TItem）”，排序时保持键值对应关系（如按ID排序订单数据）； |
//|  2. 自定义比较器：通过 IComparer<TKey> 接口支持自定义排序规则（升序/降序/按字段排序等）； |
//|  3. 自适应调整：根据数据量大小和递归深度自动切换排序算法，无需用户干预； |
//|  4. 高效稳定：最坏时间复杂度 O(n log n)，平均性能接近快速排序，适用于大规模数据； |
//| 适用场景：所有需要“高效且稳定排序”的场景，尤其适合数据量不确定或可能出现极端分布（如已排序/逆序）的数据，典型如： |
//|  - 通用数组排序（如用户列表、订单数据、日志记录等，数据量从几十到几万不等）； |
//|  - 键值对排序（如按价格排序K线数据、按时间排序交易记录，需保持键与值的对应关系）； |
//|  - 高性能排序需求（如高频交易中的数据预处理、大规模数据报表生成，对排序速度敏感）； |
//|  - 避免排序性能抖动（如框架级组件，需保证不同数据分布下的排序效率稳定）； |
//+------------------------------------------------------------------+
template<typename TKey, typename TItem>
struct Introsort
  {
public:
   IComparer<TKey>*  comparer;  // 键的比较器（实现 IComparer<TKey> 接口，定义排序规则，如升序/降序）
   TKey              keys[];    // 待排序的“键数组”（排序的依据，如ID、价格、时间戳）
   TItem             items[];   // 待排序的“值数组”（与键数组一一对应，排序时同步交换，保持关联关系）

   /**
    * @brief 默认构造函数：创建内省排序实例
    * @note 构造后需手动初始化 comparer、keys、items（如绑定比较器、赋值数组），再调用 Sort 方法
    */
                     Introsort(void);

   /**
    * @brief 析构函数：清理内省排序资源
    * @note 不负责释放外部传入的 comparer、keys、items（需用户自行管理其生命周期）
    */
                    ~Introsort(void);

   /**
    * @brief 核心排序方法：对键数组和值数组的指定范围进行排序
    * @param index [in] 排序起始索引（≥0，对应 keys 和 items 数组的起始位置）
    * @param length [in] 排序元素数量（≥0，若 length < 2 则直接返回，无需排序）
    * @note 排序逻辑：根据数据量和递归深度自动选择插入排序/快速排序/堆排序，排序后 keys 数组按比较器规则有序，items 数组与 keys 保持对应关系
    */
   void              Sort(const int index, const int length);

private:
   //----------------------------------------------------------------
   // 内省排序核心辅助方法（不对外暴露，仅内部调用）
   //----------------------------------------------------------------
   /**
    * @brief 内省排序主逻辑：控制算法切换（快速排序→堆排序）和递归深度
    * @param lo [in] 排序区间左边界（包含）
    * @param hi [in] 排序区间右边界（包含）
    * @param depthLimit [in] 递归深度上限（超过则切换为堆排序，默认值为 2*log2(n)，n 为数组长度）
    */
   void              IntroSort(const int lo, const int hi, int depthLimit);

   /**
    * @brief 快速排序的基准值选择与分区：通过“三数取中”选择基准值（避免极端数据分布），并将数组分为“小于基准”和“大于基准”两部分
    * @param lo [in] 分区区间左边界
    * @param hi [in] 分区区间右边界
    * @return int - 基准值最终位置索引（左侧元素 ≤ 基准值，右侧元素 ≥ 基准值）
    */
   int               PickPivotAndPartition(const int lo, const int hi);

   /**
    * @brief 插入排序：用于小数据量（≤16个元素）排序，简单高效
    * @param lo [in] 排序区间左边界
    * @param hi [in] 排序区间右边界
    * @note 插入排序对近乎有序的数据效率极高，适合小数据集或快速排序后的局部排序
    */
   void              InsertionSort(const int lo, const int hi);

   //----------------------------------------------------------------
   // 堆排序辅助方法（不对外暴露，仅在递归深度超限时调用）
   //----------------------------------------------------------------
   /**
    * @brief 堆排序：用于递归深度超限时，保证最坏时间复杂度 O(n log n)
    * @param lo [in] 排序区间左边界
    * @param hi [in] 排序区间右边界
    * @note 堆排序通过构建大根堆（或小根堆），反复提取堆顶元素实现排序，稳定性高于快速排序的最坏情况
    */
   void              Heapsort(const int lo, const int hi);

   /**
    * @brief 堆调整（下滤）：维护堆的性质（确保父节点 ≥ 子节点，大根堆）
    * @param i [in] 当前需要调整的堆节点索引（相对于堆的局部索引）
    * @param n [in] 堆的大小（元素数量）
    * @param lo [in] 堆在原数组中的左边界偏移量
    */
   void              DownHeap(const int i, const int n, const int lo);

   //----------------------------------------------------------------
   // 交换操作辅助方法（不对外暴露，保证键值数组同步交换）
   //----------------------------------------------------------------
   /**
    * @brief 条件交换：若 keys[a] > keys[b]，则交换 keys[a] 与 keys[b]，并同步交换 items 数组对应位置元素
    * @param a [in] 数组索引 a
    * @param b [in] 数组索引 b
    * @note 用于局部排序（如三数取中时的基准值调整），避免不必要的交换
    */
   void              SwapIfGreaterWithItems(const int a, const int b);

   /**
    * @brief 强制交换：交换 keys 数组索引 i 和 j 的元素，并同步交换 items 数组对应位置元素
    * @param i [in] 数组索引 i
    * @param j [in] 数组索引 j
    * @note 用于分区、堆排序等场景，确保键值对应关系不被破坏
    */
   void              Swap(const int i, const int j);

   //----------------------------------------------------------------
   // 工具方法（不对外暴露，支持核心逻辑）
   //----------------------------------------------------------------
   /**
    * @brief 计算 2 的对数的下取整（floor(log2(n))）
    * @param n [in] 输入值（数组长度或区间大小）
    * @return int - 下取整后的结果（用于计算递归深度上限：2*floor(log2(n))）
    */
   int               FloorLog2(int n) const;
  };
//+------------------------------------------------------------------+